package binary_tree

import "container/list"

func GetMaxDepthWithMap(root *Node) int {
	if root == nil {return 0}
	leveMap := map[*Node]int{}
	queue := list.New()
	queue.PushBack(root)
	curNodeLevel := 1
	curLevel := 1
	leveMap[root] = curNodeLevel
	var cur *Node
	curNodes, ans := 0, 0
	for queue.Len() > 0 {
		cur = queue.Remove(queue.Front()).(*Node)
		curNodeLevel = leveMap[cur]
		if cur.Left != nil {
			queue.PushBack(cur.Left)
			leveMap[cur.Left] = curNodeLevel+1
		}
		if cur.Right != nil {
			queue.PushBack(cur.Right)
			leveMap[cur.Right] = curNodeLevel+1
		}
		if curNodeLevel == curLevel {
			curNodes++
		} else {
			ans = max(ans, curNodes)
			curNodes = 1
			curLevel++
		}
	}
	ans = max(ans, curNodes)
	return ans
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func GetMaxDepthWithoutMap(root *Node) int {
	if root == nil {return 0}
	queue := list.New()
	queue.PushBack(root)
	curEnd := root
	var nextEnd *Node
	var cur *Node
	curNodes, ans := 0, 0
	for queue.Len() > 0 {
		cur = queue.Remove(queue.Front()).(*Node)
		if cur.Left != nil {
			queue.PushBack(cur.Left)
			nextEnd = cur.Left
		}
		if cur.Right != nil {
			queue.PushBack(cur.Right)
			nextEnd = cur.Right
		}
		curNodes++
		if cur == curEnd {
			ans = max(ans, curNodes)
			curNodes = 0
			curEnd = nextEnd
		}
	}
	return ans
}


